package com.mango.leet.code.middle;

/**
 * 1305. 两棵二叉搜索树中的所有元素
 * @Author: mango
 * @Date: 2022/5/1 4:28 下午
 */

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 给你 root1 和 root2 这两棵二叉搜索树。请你返回一个列表，其中包含 两棵树 中的所有整数并按 升序 排序。.
 *
 *  
 *
 * 示例 1：
 *
 *
 *
 * 输入：root1 = [2,1,4], root2 = [1,0,3]
 * 输出：[0,1,1,2,3,4]
 * 示例 2：
 *
 *
 *
 * 输入：root1 = [1,null,8], root2 = [8,1]
 * 输出：[1,1,8,8]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/all-elements-in-two-binary-search-trees
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LC1305 {
    /**
     * Definition for a binary tree node.
     */ public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode() {}
          TreeNode(int val) { this.val = val; }
          TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
              this.left = left;
              this.right = right;
          }
      }

    class Solution {
         // 中序遍历 + 合并
        public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
            List<Integer> result1 = new ArrayList<>();
            List<Integer> result2 = new ArrayList<>();
            process(root1,result1);
            process(root2,result2);
            List<Integer> result = merge(result1,result2);
            return result;
        }

        private List<Integer> merge(List<Integer> result1, List<Integer> result2) {
            List<Integer> result = new ArrayList<>();
            int left=0;
            int right=0;
            while(left < result1.size() && right < result2.size()){
                if(result1.get(left) <= result2.get(right)){
                    result.add(result1.get(left++));
                }else{
                    result.add(result2.get(right++));
                }
            }
            while (left < result1.size()){
                result.add(result1.get(left++));
            }
            while (right < result2.size()){
                result.add(result2.get(right++));
            }
            return result;
        }

        public void process(TreeNode node,List<Integer> result){
            if(node == null){
               return ;
            }
            process(node.left,result);
            result.add(node.val);
            process(node.right,result);
        }

         // 优先级队列
        public List<Integer> getAllElements2(TreeNode root1, TreeNode root2) {
            List<Integer> result = new ArrayList<>();
            PriorityQueue<Integer> pq = new PriorityQueue<>();
            process(root1,pq);
            process(root2,pq);
            while (!pq.isEmpty()){
                result.add(pq.poll());
            }
            return result;
        }

        public void process(TreeNode node,PriorityQueue pq){
            if(null == node){
                return ;
            }
            pq.offer(node.val);
            process(node.left,pq);
            process(node.right,pq);
        }
    }
}
